COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\def\xskip{\hskip7pt plus3pt minus4pt}
C00013 ENDMK
C⊗;
\def\xskip{\hskip7pt plus3pt minus4pt}
\catcode`|=13
\def|#1|{\hbox{\it#1\/}}
\parindent 0pt
\parskip 4pt
\catcode`⊗=13
\def⊗{\hbox to 2em{}}
\def\IF{\mathop{\bf if}}
\def\THEN{\mathrel{\bf then}}
\def\ELSE{\mathrel{\bf else}}
\def\AND{\mathrel{\bf and}}
\def\OR{\mathrel{\bf or}}
\def\NOT{\mathop{\bf not}}
\def\N{\mathop{\bf n}}
\def\T{\hbox{\tt T}}
\def\NIL{\hbox{\tt NIL}}
\def\.{\mathbin{.}}
\def\A{\mathop{\bf a}}
\def\D{\mathop{\bf d}}
\def\EQ{\mathrel{\bf eq}}
\def\AT{\mathop{\bf at}}
\def\PROG{\hbox{\bf program}}
\def\RETURN{\mathop{\bf return}}
\def\GOTO{\mathop{\bf go\,to}}
\def\quote#1{\hbox{\sfcode`.=1000\tt#1}}
\def\list#1{\langle#1\rangle}

\ctrline{\bf CS 206---Recursive Programming and Proving}
\vskip 20pt
\ctrline{Term Project}
\ctrline{Due Tuesday, December 14, 1982}
\vskip 10pt

	A term project is not required in order to pass CS206 or even to
get a grade of B if your homework and exams are good enough.  However, if
you wish to get some flavor of A then doing a good term project is necessary.
Term projects will be due on the day of the final exam.  Any term project
turned in ahead of time will be likely to get a more thorough reading.

	The term project is your opportunity to direct your attention
to and get experience in some area that interests you.
We ask that you do one of the four specific projects presented below,
though a convincing argument for doing some other project may be
accepted.  Any such project should be cleared with the instructor or
the TA before you begin work.

	The write-up of your project is the main thing that will get
graded so it should be clear and carefully done.  It should include
a brief description of what you set out to do and what you accomplished.
If you write a progam, you should give a description of how it works
and why, including a description of the data structures it is acting
on and the basic operations on these structures.  The code
for the program should be included with brief comments in appropriate
places to guide the reader.  Some sample runs should also be included.

\vskip 20pt
\hbox{\bf Projects:}
\vskip 10pt
{\bf 1}. {\sl Compiling}.  Modify the {\tt LCOM4} compiler discussed in
chapter VIII of the text to compile tail-recursive function calls as
simple jumps.  The simplest case of a tail-recursive function is
one that ends by calling itself.  For example,
$$|rev|[u,v]←\IF\N u\THEN v\ELSE |rev|[\D u,\A u\.v]$$
is tail-recursive; it can be compiled as if it were
$$\lpile{|rev|[u,v]←\PROG[]\cr
\hbox to 0pt{$a$:\hss}⊗\IF\N u\THEN\RETURN v;\cr
⊗v←\A u\.v;\cr
⊗u←\D u;\cr
⊗\GOTO a].\cr}$$
Other functions, like
$$|append|[u,v]←\IF\N u\THEN v\ELSE\A u\.|append|[\D u,v],$$
must use a {\tt PUSHJ} for the recursive call, but the final sequence of
calling |cons| and then returning can be replaced by simply setting up the
arguments and jumping to |cons|.

The source for the compiler is available on LOTSB as the file
{\tt BX:<EKL>LCOM4.LSP}.

\vskip 10pt
{\bf 2}. {\sl Proving}. Prove the correctness of the |samefringe| function,
as in the beginning of chapter IV of the text, using EKL.

\vskip 10pt
{\bf 3}. {\sl Simplification}. Write a simplifier for algebraic expressions.
It should accept input of the following form:
\item{$\bullet$} Numeric atoms, representing constants.
\item{$\bullet$} Non-numeric atoms, representing variables.
\item{$\bullet$} Lists of the form
$$\vbox{\halign{\tt #\hfill\cr
(PLUS $a$ $b$ $\ldots$ $k$)\cr
(TIMES $a$ $b$ $\ldots$ $k$)\cr
(DIFFERENCE $a$ $b$)\cr
(QUOTIENT $a$ $b$)\cr}}$$
where the number of arguments to {\tt PLUS} and {\tt TIMES} is variable
(possibly 0 or 1).

In addition to the simplifications done in problem 4 on the midterm exam,
your program should
\item{$\bullet$} Perform arithmetic on constants as much as possible.  This
includes things like reducing $2+x+3+y$ to $5+x+y$.
\item{$\bullet$} Combine sums that are terms of sums and products that are
factors in products.
\item{$\bullet$} Combine instances of variables into simplified polynomials,
for example converting $(2x↑2+x)y-(3xy-1)$ into $2x↑2y-xy+1$.

Many more simplifications are possible; be sure to document those that your
program does and give examples.

\vskip 10pt
\catcode`"=13
\let"=\ 
{\bf 4}. {\sl LISP macros}. Write a |let-by-need| macro.  This is similar to the
|let| macro of MacLisp, and will have the syntax
$$\vbox{\tt\halign{#\hfill\cr
(LET-BY-NEED ((var1 val1)\cr
"""""""""""""""""...\cr
""""""""""""""(varn valn))\cr
"""""""""""""body)\cr}}$$
Each {\tt var} is an atom, each {\tt val} is any Lisp form that can be
evaluated, and {\tt body} is a Lisp form.  The difference between |let|
and |let-by-need| is that while |let| first evaluates all the {\tt val}s,
binds them to the {\tt var}s, and then evaluates the {\tt body},
|let-by-need| will only evaluate a {\tt val} if it is actually needed in
the computation of the {\tt body}.  No {\tt val} is evaluated more than
once, though.  The idea is that the user of a |let-by-need| may be using
macros in {\tt body} which do not always use all of their arguments;
rather than making special-purpose versions of these macros which are
more efficient for the particular application, |let-by-need| is used to
cause the minimum amount of evaluation to be done.

For example, in
$$\vbox{\tt\halign{#\hfill\cr
(let-by-need ((x (f a b))\cr
""""""""""""""(y (g a b c)))\cr
"""""""""""""(if (h b) (foo x a) (foo b y)))\cr}}$$
we will need to evaluate only one of \quote{(f a b)} and \quote{(g a b c)},
never both.  This could be expanded as
$$\vbox{\tt\halign{#\hfill\cr
(if (h b)\cr
""""(let ((x (f a b))) (foo x a))\cr
""""(let ((y (g a b c))) (foo b y)))\cr}}$$
using the ordinary |let| macro in our output.  If the condition of an
|if|-expression is itself a condition, for example
$$\vbox{\tt\halign{#\hfill\cr
(let-by-need ((y (foo x)))\cr
"""""""""""""(if (if q (p y) r)\cr
"""""""""""""""""(a y)\cr
"""""""""""""""""b))\cr}}$$
then in order to compute \quote{(foo x)} exactly once only when it is
needed, the output would be
$$\vbox{\tt\halign{#\hfill\cr
(if q\cr
""""(let ((y (foo x)))\cr
"""""""""(if (p y) (a y) b))\cr
""""(if r (a (foo x)) b))\cr}}$$
{\tt LET-BY-NEED} has to deal correctly with input containing {\tt IF},
{\tt COND}, {\tt AND}\xskip (i.e., in {\tt (AND x y)}, forms needed only
in {\tt y} are not evaluated if {\tt x} is \NIL), {\tt OR}, and {\tt LAMBDA}.

\vfill\end